/**
 * @author DCSGO
 * @version 1.0
 */
class ListNode{
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class MyLinkedList {
    public ListNode dummyHead;
    public int size;

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtTail(1);
        myLinkedList.addAtTail(3);
        System.out.println(myLinkedList.get(1));
        System.out.println(myLinkedList.get(0));

    }

    public MyLinkedList() {
        dummyHead=new ListNode(0,null);
        size=0;
    }

    public int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        //遍历节点
        ListNode cur=dummyHead.next;
        while(index>0){
            cur=cur.next;
            index--;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newNode=new ListNode(val);
        newNode.next=dummyHead.next;
        dummyHead.next=newNode;
        size++;
    }

    public void addAtTail(int val) {
        if(size==0){//链表为空进行头插
            addAtHead(val);
            return;
        }
        ListNode cur=dummyHead.next;
        ListNode newNode=new ListNode(val,null);
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=newNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if(index<0||index>size){
            return;
        }
        if(index==size){
            addAtTail(val);
            return;
        }
        ListNode newNode=new ListNode(val);
        ListNode pre=dummyHead;
        ListNode cur=pre.next;
        while(index>0){
            pre=cur;
            cur=cur.next;
            index--;
        }
        //插入新节点
        newNode.next=cur;
        pre.next=newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        ListNode pre=dummyHead;
        ListNode cur=pre.next;
        while(index>0){
            pre=cur;
            cur=cur.next;
            index--;
        }
        //删除该节点
        pre.next=cur.next;
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */